import java.util.Scanner;

public class Test2 {
    //完全背包
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), V = sc.nextInt();
        int[] v = new int[n + 1], w = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        //状态表示：dp[i][j]表示从前i个物品中挑选物品，装入背包容量为j的背包中，使得背包能装下时背包中物品的最大价值
        int[][] dp = new int[n + 1][V + 1];
        //状态转移方程：如果当前第i个不选，那么dp[i][j] = dp[i-1][j]
        //当选择装入第i个物品的时候，因为第i个物品的数量有无数个，所以需要将这些情况都考虑到，dp[i][j] = Math.max(dp[i][j],dp[i-1][j-v[i]] + w[i],dp[i-1][j-2v[i]] + 2w[i]...)
        //dp[i][j-v[i]] = Math.max(dp[i-1][j-v[i]],dp[i-1][j-2v[i]] + w[i],dp[i-1][j-3v[i]] + 2v[i])
        //所以dp[i][j] = Math.max(dp[i-1][j],dp[i][j - v[i]] + w[i]);

        //初始化，这里需要用到i-1和j-v[i]的值，保证j>=v[i]，那么需要初始化的就是当i为0的时候
        //填表顺序，当填第i列的时候需要用到i-1列，所以是从上往下，但是填第j列的时候需要用到j-v[i]列，所以需要从左往右
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= V; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= v[i]) dp[i][j] = Math.max(dp[i][j],dp[i][j - v[i]] + w[i]);
            }
        }
        System.out.println(dp[n][V]);

        for (int i = 1; i <= V; i++) dp[0][i] = -1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= V; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= v[i] && dp[i][j-v[i]] != -1 ) dp[i][j] = Math.max(dp[i][j],dp[i][j - v[i]] + w[i]);
            }
        }
        System.out.println(dp[n][V] == -1 ? 0 : dp[n][V]);
    }

    //优化
    public static void main1(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), V = sc.nextInt();
        int[] v = new int[n + 1], w = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        //状态表示：dp[i][j]表示从前i个物品中挑选物品，装入背包容量为j的背包中，使得背包能装下时背包中物品的最大价值
        int[] dp = new int[V + 1];
        //状态转移方程：如果当前第i个不选，那么dp[i][j] = dp[i-1][j]
        //当选择装入第i个物品的时候，因为第i个物品的数量有无数个，所以需要将这些情况都考虑到，dp[i][j] = Math.max(dp[i][j],dp[i-1][j-v[i]] + w[i],dp[i-1][j-2v[i]] + 2w[i]...)
        //dp[i][j-v[i]] = Math.max(dp[i-1][j-v[i]],dp[i-1][j-2v[i]] + w[i],dp[i-1][j-3v[i]] + 2v[i])
        //所以dp[i][j] = Math.max(dp[i-1][j],dp[i][j - v[i]] + w[i]);

        //初始化，这里需要用到i-1和j-v[i]的值，保证j>=v[i]，那么需要初始化的就是当i为0的时候
        //填表顺序，当填第i列的时候需要用到i-1列，所以是从上往下，但是填第j列的时候需要用到j-v[i]列，所以需要从左往右
        for (int i = 1; i <= n; i++) {
            for (int j = v[i]; j <= V; j++) {
                dp[j] = dp[j];
                if (j >= v[i]) dp[j] = Math.max(dp[j],dp[j - v[i]] + w[i]);
            }
        }
        System.out.println(dp[V]);

        for (int i = 1; i <= V; i++) dp[i] = -1;
        for (int i = 1; i <= n; i++) {
            for (int j = v[i]; j <= V; j++) {
                dp[j] = dp[j];
                if (j >= v[i] && dp[j-v[i]] != -1 ) dp[j] = Math.max(dp[j],dp[j - v[i]] + w[i]);
            }
        }
        System.out.println(dp[V] == -1 ? 0 : dp[V]);
    }
}
